package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *RestoreIPAddresses_93 给一个字符串 输出其所有正确IP的字符串集合
 *describe:一个正确的IP 包含3个.和4个0-255区间的整数  用回溯法暴力解决 AC 98% 其中注意0输入的情况
 *2018年5月18日 下午9:08:42
 */
public class RestoreIPAddresses_93 {
	List<String> res;
	String s;
	public static void main(String[] args) {
		RestoreIPAddresses_93 test=new RestoreIPAddresses_93();
		//test.restoreIpAddresses("25525511135");
		test.restoreIpAddresses("0000");

	}
	
	public List<String> restoreIpAddresses(String s) {
		this.res=new ArrayList<String>();
		this.s=s;
		help(new StringBuilder(),0,0,0);
        return this.res;
    }
	
	/**
	 * describe: 有两种情况before是0  第一 集合最后一位是
	 * 2018年5月18日 下午8:05:12
	 * @param sb 当前String子集合
	 * @param before 之前的整数总数
	 * @param index 指向原字符串第i个字符 该如何处理该字符 是在此处添加. 还是并入
	 * @param pointCount 当前的.数量
	 */
	public void help(StringBuilder sb,int before,int index,int pointCount) {
		if(pointCount>3||index>s.length())
			return ;
		if(index==this.s.length()) {
			if(pointCount==3&&sb.charAt(sb.length()-1)!='.')
				this.res.add(sb.toString());
			return;
		}
		char beforeChar='.';
		if(sb.length()!=0)
			 beforeChar=sb.charAt(sb.length()-1);
		char now=s.charAt(index);
		if(now=='0') {//特殊情况 0必须并入前面的数 或者另开辟.
			if(sb.length()==0||beforeChar=='.') {//前面是.或者第一个是0
				sb.append('0');
				if(pointCount==3&&index==this.s.length()-1) {//可以并入
					this.res.add(sb.toString());
					sb.delete(sb.length()-1, sb.length());
					return ;
				}
				else {
					sb.append('.');//开辟新的.
					help(sb,0,index+1,pointCount+1);
					sb.delete(sb.length()-2, sb.length());//回退
				}
			}
			else {//前面是数字
				int count=before*10+(now-'0');
				if(count<=255) {//此数填入是合法地址
					sb.append(now);
					help(sb,count,index+1,pointCount);
					sb.delete(sb.length()-1, sb.length());
				}
				if(beforeChar!='.') {
					sb.append('.');
					help(sb,0,index,pointCount+1);
					sb.delete(sb.length()-1, sb.length());
				}
			}
		}
		else {
			int count=before*10+(now-'0');
			if(count<=255) {//此数填入是合法地址
				sb.append(now);
				help(sb,count,index+1,pointCount);
				sb.delete(sb.length()-1, sb.length());
			}
			if(beforeChar!='.') {
				sb.append('.');
				help(sb,0,index,pointCount+1);
				sb.delete(sb.length()-1, sb.length());
			}
		}	
	}

}
